package org.shj.suanfa

/**
 * 本例演示二进制的一些使用
 */
object BinaryNumber {
  def main(args: Array[String]): Unit = {
    aplusb(10, 2)
    
    /**
     *  x & (x-1) 用于消去 x 最后一位的1
     *  x = 1100
     *  x-1= 1011
     *  x & (x-1) = 1000
     */
    checkPowerOf2(4)
    bitSwapRequire(5, 8)
    
    /**
     * a^b^b = a
     */
    findShowOnce()
    
  }
  
  /**
   * 数组中只有一个数出现一次，剩下的都出现两次，找出出现一次的数
   */
  def findShowOnce(){
    val arr = Array[Int](3,6, 8, 9, 8, 6 ,3)
    val once = arr.reduce(_^_)
    println(once + " 仅出现过一次")
  }
  
  /**
   *  用 O(1)时间检测整数n是否是2的幂次
   *  如果是 2的幂次，则N满足两个条件：
   *  1. N > 0
   *  2. N 的二进制表示中只有一个1
   *  因为只有一个1，所以消去最后一个1后，为0
   */
  def checkPowerOf2(n: Int){
    val is = n > 0 && (n & (n - 1)) == 0 
    println(n + " " + (if(is) "is" else "isn't") + " the power of 2.")
  }
  
  /**
   * 将a转化成b，需要改变多少个bit
   * 思路： 只需要改变 a 和 b 在相同位置上值不同的地方，也就是求a和b有多少个bit位不相同。
   *    位运算中有个异或操作，相同为0，相异为1，问题就转换成了求a和b异或操作后，有多少个1
   */
  def bitSwapRequire(a: Int, b: Int) {
    var c = a ^ b
    var cnt = 0
    while(c != 0){
      c = c & (c-1)
      cnt += 1
    }
    println(s"$a 要转换成 $b 需要改变 $cnt 位")
  }
  
  /**
   * 不使用 + 运算，计算 a+b 的值
   * 主要利用异或运算来完成。异或运算有一个别名，叫做不进位加法
   * 那么 a^b 就是a和b相加之后，该进位的地方不进位的结果
   * 然后下面考虑哪些地方要进位，自然是a和b里都是1的地方
   * a&b 就是a和b里都是1的那些位置， a&b << 1 就是进位之后的结果，
   * 所以 a+b = (a^b) + (a&b <<1)
   * 令 a' = a^b,  b'= a&b <<1
   * 可以知道，这个过程是在模拟加法的运算过程，进位不可能一直持续，所以b最终
   * 会变为0，因此重复上面的操作就可以得到a+b的值  
   * 
   */
  def aplusb(a: Int, b: Int){
    var a0 = a
    var b0 = b
    while(b0 != 0){
      var a1 = a0 ^ b0
      var b1 = (a0 & b0) << 1
      a0 = a1
      b0 = b1
    }
    println(s"$a + $b = $a0")
  }
}